In multiprocessor systems (both tightly and loosely coupled), it is necessary to control the accesses of the processors to shared data or shared functions or resources. A facility providing the necessary control mechanism is called a "locking" or "synchronization" facility. Since the locking/synchronization facility must be available to all processors in the system, it is often the case that the facility must run on special-purpose hardware that supports communication with all of the processors. The result is that development costs for such a facility can be very high.
A solution to this problem is to design "general" locking/synchronization facilities that can be easily modified or extended, and that can be tailored to particular applications. One way to provide such a facility is to encode all state transitions of the locks or synchronization entities in a transition table. For example, assume that each lock or synchronization entity L can be in one of n states, S1-Sn, and that each of the p processors P1-Pp can issue any of r requests R1-Rr against L. The state-transition behavior of the locking/synchronization facility can then be specified by a transition table T consisting of s.multidot.p.multidot.r entries, where each entry T[i,j,k] gives the new state of a lock currently in the state Si when request Rj is made by processor Pk.
A simple example of a transition table is given below in Table I for a system employing p=2 processors and having exclusive locks with three states: S1=unlocked, S2=locked-by-P1 and S3=locked-by-P2, with the available requests comprising R1=lock and R2=unlocked.
TABLE I ______________________________________ Si Rj Pk T[i,j,k] ______________________________________ unlocked unlock P1 unlocked unlocked unlock P2 unlocked unlocked lock P1 locked-by-P1 unlocked lock P2 locked-by-P2 locked-by-P1 unlock P1 unlocked locked-by-P1 unlock P2 locked-by-P1 locked-by-P1 lock P1 locked-by-P1 locked-by-P1 lock P2 locked-by-P1 locked-by-P2 unlock P1 locked-by-P2 locked-by-P2 unlock P2 unlocked locked-by-P2 lock P1 locked-by-P2 locked-by-P2 lock P2 locked-by-P2 ______________________________________
As locks change states, certain processors may be interested in the transition, depending on the state change. In particular, it is usually the case that a processor is interested in the result of a lock request that it has just issued. The details of the communication of the lock name and new lock state to interested processors depend on the hardware that is being used to support the locking/synchronization facility. Also, it may be the case that this information is buffered. Here it will simply be assumed that it is possible to transmit this information to all interested processors. In order to determine which processors are interested in a particular transition, a boolean "notify vector" N[i,j,k] will be associated with each transition table entry T[i,j,k].
For example, a simple notify vector N[i,j,k] could be a k-bit vector with one bit corresponding to each of the k processors and the value of each bit indicating whether or not the corresponding processor should be notified for the particular state transition. Thus, if N[i,j,k][k'], 1.ltoreq.k'.ltoreq.k, lock name L and new state T[i,j,k] will be sent to processor Pk' (or put into a buffer for processor Pk') when processor Pk issues request Rj against a lock L currently in state Si.
For example, it may be desired to extend the exclusive lock facility described above in Table I to include two new states: S4=locked-by-P1-P2-waiting and S5=locked-by-P2-P1-waiting. It may be further desired that: (1) if a lock is held by one of the processors and the other goes into a wait on the lock, the first processor will be notified; (2) if a processor, e.g., P1, is waiting for a lock held by P2, the lock state will become locked-by-P1 when P2 releases the lock, and P1 will be notified; and (3) P1 and P2 are always interested in the results of their own lock requests. With these assumptions, T and N would be as shown below in Table II.
TABLE II ______________________________________ Si Rj Pk T[i,j,k] N[i,j,k] ______________________________________ unlocked unlock P1 unlocked 1,0 unlocked unlock P2 unlocked 0,1 unlocked lock P1 locked-by-P1 1,0 unlocked lock P2 locked-by-P2 0,1 locked-by-P1 unlock P1 unlocked 1,0 locked-by-P1 unlock P2 locked-by-P1 0,1 locked-by-P1 lock P1 locked-by-P1 1,0 locked-by-P1 lock P2 lckd-by-P1-P2-wait 1,1 locked-by-P2 unlock P1 locked-by-P2 1,0 locked-by-P2 unlock P2 unlocked 0,1 locked-by-P2 lock P1 lckd-by-P2-P1-wait 1,1 locked-by-P2 lock P2 locked-by-P2 0,1 lckd-by-P1-P2-wait unlock P1 locked-by-P2 1,1 lckd-by-P1-P2-wait unlock P2 locked-by-P1 0,1 lckd-by-P1-P2-wait lock P1 lckd-by-P1-P2-wait 1,0 lckd-by-P1-P2-wait lock P2 lckd-by-P1-P2-wait 0,1 lckd-by-P2-P1-wait unlock P1 locked-by-P2 1,0 lckd-by-P2-P1-wait unlock P2 locked-by-P1 1,1 lckd-by-P2-P1-wait lock P1 lckd-by-P2-P1-wait 1,0 lckd-by-P2-P1-wait lock P2 lckd-by-P2-P1-wait 0,1 ______________________________________
In summary, a straight forward locking/synchronization facility using conventional table-driven techniques would operate as follows:
1. A request Rj against the lock L is received from processor Pk. PA0 2. The system looks up the current state of lock L, e.g., Si. PA0 3. The state of L is set to T[i,j,k]. PA0 4. For 1.ltoreq.k'.ltoreq.p, if N[i,j,k][k'], then (L,T[i,j,k]) will be sent to processor Pk'.
If it were desired to extend the exclusive lock facility with five lock states described above to support eight processors, with queueing of processors waiting on a lock, the number of states would increase substantially. For example, there would then states such as "locked by P1, P2 waiting on P1, P3 waiting on P2, P4 waiting on P3" (such a state will hereinafter be expressed by the notation P4.fwdarw.P3.fwdarw.P2.fwdarw.P1), and the total number of states would be the unlocked state, plus locked by any one of the eight processors, plus locked by any one of the eight processors and any one of the remaining seven processors waiting, etc., and would be calculated by: EQU 1+8+8.multidot.7+8.multidot.7.multidot.6+ . . . +8.multidot.7.multidot.6.multidot.5.multidot.4.multidot.3.multidot.2.multi dot.1=109,601.
Thus, the combinational explosion of lock states makes a straight forward table-driven locking/synchronization facility impractical for applications such as the one illustrated by the above example, and practical only for the simplest kinds of locking/synchronization facilities.